package com.sicheng.lc.杂题.滑动窗口专题;

import java.util.HashMap;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/12 21:04
 */
public class 至少有K个重复字符的最长子串 {
    //https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/


    static HashMap<Character, Integer> map = new HashMap<>(64);

    {
        map.clear();
    }

    public int longestSubstring(String s, int k) {

        int max = -1;
        int state = 0;
        for (int i = 0; i < s.length(); i++) {
            state |= (1 << (s.charAt(i) - 'a'));
        }
        int m = 0;
        while (state > 0) {
            state &= state - 1;
            m++;
        }
        for (int i = 1; i <= m; i++) {
            for (int r = 0, l = 0; r < s.length(); r++) {
                map.put(s.charAt(r), map.getOrDefault(s.charAt(r), 0) + 1);
                while (!check(i)) {
                    map.put(s.charAt(l), map.get(s.charAt(l)) - 1);
                    l++;
                }
                if (ok(k))
                    max = Math.max(max, r - l + 1);
            }
            map.clear();
        }
        return max;
    }

    private boolean ok(int k) {
        for (int x : map.values()) {
            if (x > 0 && x < k)
                return false;
        }

        return true;
    }

    private boolean check(int i) {
        int cnt = 0;
        for (int v : map.values()) {
            if (v > 0)
                cnt++;
        }
        return cnt <= i;
    }

    public static void main(String[] args) {
        至少有K个重复字符的最长子串 s = new 至少有K个重复字符的最长子串();
        System.out.println(s.longestSubstring("bbaaacbd", 3));
    }
}
